# -*- coding: utf-8 -*-
'''
@Time    : 2022/8/9 11:01
@Author  : HandsomeWu
@File    : magicBone.py
@Describe: 魔法石
        给n个双面硬币，硬币正面反面印着一个数字 求让同一面向上的翻动最少次数
* input:
    石头个数
    石头正面的数
    石头反面的数

* output:
    需要翻面的最少次数

'''
import math

def magic_bone(N,T1,T2):

    # Step 1: 统计正反面类别数
    up_count = {}
    down_count = {}
    for i in range(N):
        a,b = T1[i],T2[i]

        # 处理正面
        if a not in up_count:
            up_count[a] = 1
        else:
            up_count[a] +=1

        # 处理反面 --  正反面相等 不记录
        if a == b:
            continue

        if b not in down_count:
            down_count[b] =1
        else:
            down_count[b] +=1

    # 这里最好将字典排序 -- 排序后就不用全部遍历了
    total_key = set(list(up_count.keys())+list(down_count.keys()))

    # Step 2: 遍历类别 找出 正+反 > 一半的类
    # 但是从正面多的入手好像也更合适 -- 万一正面全是1个的 反面有一样的 怎么办 -- 考虑这种情况
    # 正反面还要防止重复遍历 -- set()

    min_time = float('inf')
    half_N = math.ceil(N/2)

    for key in total_key:
        if key in up_count and key in down_count:
            # 正反面都有
            total = up_count[key] + down_count[key]
            if total >= half_N:
                min_time = min(min_time, max(half_N - up_count[key],0))  # 计算有多少需要翻过来

        elif key in up_count and key not in down_count:
            # 正有 反面没有
            total = up_count[key]
            if total >= half_N:
                return min_time
        else:
            # 正面没有 反面有
            total = down_count[key]
            if total >= half_N:
                min_time = min( half_N,min_time)

    return -1 if min_time == float('inf') else min_time



if __name__ == '__main__':
    T = 5
    list1 = [1,5,7,5,5]
    list2 = [10,5,5,9,10]
    out = magic_bone(T,list1,list2)
    print(out)








